Năm 642, người Ả Rập chinh phục Ai Cập. Ngay sau khi đặt chân đến trước các kim tự tháp ở Giza, họ đã đi tìm lời giải về việc ai là người đã xây dựng nên các công trình này. Tuy nhiên, vào lúc đó, không còn bất kỳ người dân Ai Cập nào có thể trả lời câu hỏi trên và cũng không còn bất cứ ai có thể dịch chữ tượng hình của người Ai Cập được nữa. Vì thế, các sử gia Ảrập đã tự sáng tạo ra những giả thuyết và câu chuyện của họ[12][48].

Câu chuyện nổi tiếng nhất về Khufu và kim tự tháp của ông có thể tìm thấy trong tác phẩm Hitat (tên đầy đủ: al-Mawā'iẓ wa-'l-i'tibār fī ḏikr al-ḫiṭaṭ wa-'l-'āṯār), được Muhammad al-Maqrizi (1364-1442) viết vào năm 1430. Cuốn sách này bao gồm tập hợp một vài giả thuyết và những câu chuyện hoang đường về Khufu, đặc biệt là về Đại Kim tự tháp. Mặc dù vậy, bản thân vua Khufu lại ít khi được đề cập đến trong những câu truyện này, không những thế nhiều tác giả Ả rập lại tin rằng Đại Kim tự tháp (cũng như những kim tự tháp khác) đã được thần Hermes (được người Ả rập gọi là Iris) xây dựng nên [12][48].

Al-Maqrizi chú giải rằng Khufu đã được người Amalek trong kinh thánh gọi tên là Saurid, Salhuk hoặc Sarjak. Tiếp đó ông ta còn viết rằng Khufu đã xây dựng các kim tự tháp sau khi ông trải qua những cơn ác mộng liên hồi về việc trái đất quay lộn ngược, các vì sao rơi xuống khỏi bầu trời còn người dân thì lại đang la hét vì sợ hãi. Một cơn ác mộng khác của ông là về các vì sao rơi xuống khỏi bầu trời và bắt cóc con người, sau đó chúng dùng hai ngọn núi lớn để đè lên họ. Vua Khufu sau đó đã nhận được một lời cảnh báo từ những nhà tiên tri của ông về một trận đại hồng thủy sẽ xảy đến và nó sẽ tàn phá Ai Cập. Để bảo vệ kho báu cùng những quyển sách thông thái của mình, Khufu đã xây dựng ba kim tự tháp ở Giza[12][48].